<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html lang = "en">

<head>

<link rel="shortcut icon" href="http://algs4.cs.princeton.edu/favicon.ico">
<link rel="stylesheet"    href="http://algs4.cs.princeton.edu/java.css" type="text/css">

<title>TwoPersonZeroSumGame.java</title>

<meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<meta NAME="AUTHOR" CONTENT="Robert Sedgewick and Kevin Wayne">
<meta NAME="DESCRIPTION" CONTENT="TwoPersonZeroSumGame code in Java">
<meta NAME="TITLE" CONTENT="TwoPersonZeroSumGame code in Java">
<meta NAME="KEYWORDS" CONTENT="TwoPersonZeroSumGame,java,programming,computer science,algorithm,data structure,program,code">
<meta NAME="ROBOTS" CONTENT="INDEX,FOLLOW">

</head>


<body>
<center><h1>TwoPersonZeroSumGame.java</h1></center><p><br>

Below is the syntax highlighted version of <a href = "TwoPersonZeroSumGame.java">TwoPersonZeroSumGame.java</a>.
<p><br>

<!-- Generator: GNU source-highlight 3.1.6
by Lorenzo Bettini
http://www.lorenzobettini.it
http://www.gnu.org/software/src-highlite -->
<pre><tt><span class="comment">/******************************************************************************</span>
<span class="comment"> *  Compilation:  javac TwoPersonZeroSumGame.java</span>
<span class="comment"> *  Execution:    java TwoPersonZeroSumGame M N</span>
<span class="comment"> *  Dependencies: LinearProgramming.java StdOut.java</span>
<span class="comment"> *</span>
<span class="comment"> *  Solve an M-by-N two-person zero-sum game by reducing it to</span>
<span class="comment"> *  linear programming. Assuming A is a strictly positive payoff</span>
<span class="comment"> *  matrix, the optimal row and column player strategies are x* an y*,</span>
<span class="comment"> *  scaled to be probability distributions.</span>
<span class="comment"> *</span>
<span class="comment"> *  (P)  max  y^T 1         (D)  min   1^T x</span>
<span class="comment"> *       s.t  A^T y &lt;= 1         s.t   A x &gt;= 1</span>
<span class="comment"> *                y &gt;= 0                 x &gt;= 0</span>
<span class="comment"> *</span>
<span class="comment"> *  Row player is x, column player is y.</span>
<span class="comment"> *</span>
<span class="comment"> ******************************************************************************/</span>

<span class="preproc">package</span><span class="normal"> edu</span><span class="symbol">.</span><span class="normal">princeton</span><span class="symbol">.</span><span class="normal">cs</span><span class="symbol">.</span><span class="normal">algs4</span><span class="symbol">;</span>

<span class="comment">/**</span>
<span class="comment"> *  The </span><span class="keyword">&lt;tt&gt;</span><span class="comment">TwoPersonZeroSumGame</span><span class="keyword">&lt;/tt&gt;</span><span class="comment"> class represents a data type for</span>
<span class="comment"> *  computing optimal row and column strategies to two-person zero-sum games.</span>
<span class="comment"> *  </span><span class="keyword">&lt;p&gt;</span>
<span class="comment"> *  This implementation solves an </span><span class="keyword">&lt;em&gt;</span><span class="comment">M</span><span class="keyword">&lt;/em&gt;</span><span class="comment">-by-</span><span class="keyword">&lt;em&gt;</span><span class="comment">N</span><span class="keyword">&lt;/em&gt;</span><span class="comment"> two-person</span>
<span class="comment"> *  zero-sum game by reducing it to a linear programming problem.</span>
<span class="comment"> *  Assuming the payoff matrix </span><span class="keyword">&lt;em&gt;</span><span class="comment">A</span><span class="keyword">&lt;/em&gt;</span><span class="comment"> is strictly positive, the</span>
<span class="comment"> *  optimal row and column player strategies x* and y* are obtained</span>
<span class="comment"> *  by solving the following primal and dual pair of linear programs,</span>
<span class="comment"> *  scaling the results to be probability distributions.</span>
<span class="comment"> *  </span><span class="keyword">&lt;p&gt;&lt;blockquote&gt;&lt;pre&gt;</span>
<span class="comment"> *  (P)  max  y^T 1         (D)  min   1^T x</span>
<span class="comment"> *       s.t  A^T y &lt;= 1         s.t   A x &gt;= 1</span>
<span class="comment"> *                y &gt;= 0                 x &gt;= 0</span>
<span class="comment"> *  </span><span class="keyword">&lt;/pre&gt;&lt;/blockquote&gt;&lt;p&gt;</span>
<span class="comment"> *  If the payoff matrix </span><span class="keyword">&lt;em&gt;</span><span class="comment">A</span><span class="keyword">&lt;/em&gt;</span><span class="comment"> has any negative entries, we add</span>
<span class="comment"> *  the same constant to every entry so that every entry is positive.</span>
<span class="comment"> *  This increases the value of the game by that constant, but does not</span>
<span class="comment"> *  change solutions to the two-person zero-sum game.</span>
<span class="comment"> *  </span><span class="keyword">&lt;p&gt;</span>
<span class="comment"> *  This implementation is not suitable for large inputs, as it calls</span>
<span class="comment"> *  a bare-bones linear programming solver that is neither fast nor</span>
<span class="comment"> *  robust with respect to floating-point roundoff error.</span>
<span class="comment"> *  </span><span class="keyword">&lt;p&gt;</span>
<span class="comment"> *  For additional documentation, see</span>
<span class="comment"> *  </span><span class="keyword">&lt;a</span><span class="normal"> </span><span class="type">href</span><span class="symbol">=</span><span class="string">"http://algs4.cs.princeton.edu/65reductions"</span><span class="keyword">&gt;</span><span class="comment">Section 6.5</span><span class="keyword">&lt;/a&gt;</span>
<span class="comment"> *  </span><span class="keyword">&lt;i&gt;</span><span class="comment">Algorithms, 4th Edition</span><span class="keyword">&lt;/i&gt;</span><span class="comment"> by Robert Sedgewick and Kevin Wayne.</span>
<span class="comment"> *</span>
<span class="comment"> *  </span><span class="type">@author</span><span class="comment"> Robert Sedgewick</span>
<span class="comment"> *  </span><span class="type">@author</span><span class="comment"> Kevin Wayne</span>
<span class="comment"> */</span>
<span class="keyword">public</span><span class="normal"> </span><span class="keyword">class</span><span class="normal"> </span><span class="classname">TwoPersonZeroSumGame</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="keyword">static</span><span class="normal"> </span><span class="keyword">final</span><span class="normal"> </span><span class="type">double</span><span class="normal"> EPSILON </span><span class="symbol">=</span><span class="normal"> </span><span class="number">1E-8</span><span class="symbol">;</span>

<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="keyword">final</span><span class="normal"> </span><span class="type">int</span><span class="normal"> M</span><span class="symbol">;</span><span class="normal">            </span><span class="comment">// number of rows</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="keyword">final</span><span class="normal"> </span><span class="type">int</span><span class="normal"> N</span><span class="symbol">;</span><span class="normal">            </span><span class="comment">// number of columns</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="usertype">LinearProgramming</span><span class="normal"> lp</span><span class="symbol">;</span><span class="normal">   </span><span class="comment">// linear program solver</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="type">double</span><span class="normal"> constant</span><span class="symbol">;</span><span class="normal">        </span><span class="comment">// constant added to each entry in payoff matrix</span>
<span class="normal">                                    </span><span class="comment">// (0 if all entries are strictly positive)</span>
<span class="normal"> </span>
<span class="normal">    </span><span class="comment">/**</span>
<span class="comment">     * Determines an optimal solution to the two-sum zero-sum game</span>
<span class="comment">     * with the specified payoff matrix.</span>
<span class="comment">     *</span>
<span class="comment">     * </span><span class="type">@param</span><span class="comment">  payoff the </span><span class="keyword">&lt;em&gt;</span><span class="comment">M</span><span class="keyword">&lt;/em&gt;</span><span class="comment">-by-</span><span class="keyword">&lt;em&gt;</span><span class="comment">N</span><span class="keyword">&lt;/em&gt;</span><span class="comment"> payoff matrix</span>
<span class="comment">     */</span><span class="normal"> </span>
<span class="normal">    </span><span class="keyword">public</span><span class="normal"> </span><span class="function">TwoPersonZeroSumGame</span><span class="symbol">(</span><span class="type">double</span><span class="symbol">[][]</span><span class="normal"> payoff</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        M </span><span class="symbol">=</span><span class="normal"> payoff</span><span class="symbol">.</span><span class="normal">length</span><span class="symbol">;</span>
<span class="normal">        N </span><span class="symbol">=</span><span class="normal"> payoff</span><span class="symbol">[</span><span class="number">0</span><span class="symbol">].</span><span class="normal">length</span><span class="symbol">;</span>

<span class="normal">        </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> c </span><span class="symbol">=</span><span class="normal"> </span><span class="keyword">new</span><span class="normal"> </span><span class="type">double</span><span class="symbol">[</span><span class="normal">N</span><span class="symbol">];</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> b </span><span class="symbol">=</span><span class="normal"> </span><span class="keyword">new</span><span class="normal"> </span><span class="type">double</span><span class="symbol">[</span><span class="normal">M</span><span class="symbol">];</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[][]</span><span class="normal"> A </span><span class="symbol">=</span><span class="normal"> </span><span class="keyword">new</span><span class="normal"> </span><span class="type">double</span><span class="symbol">[</span><span class="normal">M</span><span class="symbol">][</span><span class="normal">N</span><span class="symbol">];</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> i </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> i </span><span class="symbol">&lt;</span><span class="normal"> M</span><span class="symbol">;</span><span class="normal"> i</span><span class="symbol">++)</span>
<span class="normal">            b</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">]</span><span class="normal"> </span><span class="symbol">=</span><span class="normal"> </span><span class="number">1.0</span><span class="symbol">;</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> j </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> j </span><span class="symbol">&lt;</span><span class="normal"> N</span><span class="symbol">;</span><span class="normal"> j</span><span class="symbol">++)</span>
<span class="normal">            c</span><span class="symbol">[</span><span class="normal">j</span><span class="symbol">]</span><span class="normal"> </span><span class="symbol">=</span><span class="normal"> </span><span class="number">1.0</span><span class="symbol">;</span>

<span class="normal">        </span><span class="comment">// find smallest entry</span>
<span class="normal">        constant </span><span class="symbol">=</span><span class="normal"> Double</span><span class="symbol">.</span><span class="normal">POSITIVE_INFINITY</span><span class="symbol">;</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> i </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> i </span><span class="symbol">&lt;</span><span class="normal"> M</span><span class="symbol">;</span><span class="normal"> i</span><span class="symbol">++)</span>
<span class="normal">            </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> j </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> j </span><span class="symbol">&lt;</span><span class="normal"> N</span><span class="symbol">;</span><span class="normal"> j</span><span class="symbol">++)</span>
<span class="normal">                </span><span class="keyword">if</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">payoff</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">][</span><span class="normal">j</span><span class="symbol">]</span><span class="normal"> </span><span class="symbol">&lt;</span><span class="normal"> constant</span><span class="symbol">)</span>
<span class="normal">                    constant </span><span class="symbol">=</span><span class="normal"> payoff</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">][</span><span class="normal">j</span><span class="symbol">];</span>

<span class="normal">        </span><span class="comment">// add constant  to every entry to make strictly positive</span>
<span class="normal">        </span><span class="keyword">if</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">constant </span><span class="symbol">&lt;=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">)</span><span class="normal"> constant </span><span class="symbol">=</span><span class="normal"> </span><span class="symbol">-</span><span class="normal">constant </span><span class="symbol">+</span><span class="normal"> </span><span class="number">1</span><span class="symbol">;</span>
<span class="normal">        </span><span class="keyword">else</span><span class="normal">               constant </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> i </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> i </span><span class="symbol">&lt;</span><span class="normal"> M</span><span class="symbol">;</span><span class="normal"> i</span><span class="symbol">++)</span>
<span class="normal">            </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> j </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> j </span><span class="symbol">&lt;</span><span class="normal"> N</span><span class="symbol">;</span><span class="normal"> j</span><span class="symbol">++)</span>
<span class="normal">                A</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">][</span><span class="normal">j</span><span class="symbol">]</span><span class="normal"> </span><span class="symbol">=</span><span class="normal"> payoff</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">][</span><span class="normal">j</span><span class="symbol">]</span><span class="normal"> </span><span class="symbol">+</span><span class="normal"> constant</span><span class="symbol">;</span>

<span class="normal">        lp </span><span class="symbol">=</span><span class="normal"> </span><span class="keyword">new</span><span class="normal"> </span><span class="function">LinearProgramming</span><span class="symbol">(</span><span class="normal">A</span><span class="symbol">,</span><span class="normal"> b</span><span class="symbol">,</span><span class="normal"> c</span><span class="symbol">);</span>

<span class="normal">        </span><span class="keyword">assert</span><span class="normal"> </span><span class="function">certifySolution</span><span class="symbol">(</span><span class="normal">payoff</span><span class="symbol">);</span>
<span class="normal">    </span><span class="cbracket">}</span>


<span class="normal">    </span><span class="comment">/**</span>
<span class="comment">     * Returns the optimal value of this two-person zero-sum game.</span>
<span class="comment">     *</span>
<span class="comment">     * </span><span class="type">@return</span><span class="comment"> the optimal value of this two-person zero-sum game</span>
<span class="comment">     *</span>
<span class="comment">     */</span>
<span class="normal">    </span><span class="keyword">public</span><span class="normal"> </span><span class="type">double</span><span class="normal"> </span><span class="function">value</span><span class="symbol">()</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="keyword">return</span><span class="normal"> </span><span class="number">1.0</span><span class="normal"> </span><span class="symbol">/</span><span class="normal"> </span><span class="function">scale</span><span class="symbol">()</span><span class="normal"> </span><span class="symbol">-</span><span class="normal"> constant</span><span class="symbol">;</span>
<span class="normal">    </span><span class="cbracket">}</span>


<span class="normal">    </span><span class="comment">// sum of x[j]</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="type">double</span><span class="normal"> </span><span class="function">scale</span><span class="symbol">()</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> x </span><span class="symbol">=</span><span class="normal"> lp</span><span class="symbol">.</span><span class="function">primal</span><span class="symbol">();</span>
<span class="normal">        </span><span class="type">double</span><span class="normal"> sum </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0.0</span><span class="symbol">;</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> j </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> j </span><span class="symbol">&lt;</span><span class="normal"> N</span><span class="symbol">;</span><span class="normal"> j</span><span class="symbol">++)</span>
<span class="normal">            sum </span><span class="symbol">+=</span><span class="normal"> x</span><span class="symbol">[</span><span class="normal">j</span><span class="symbol">];</span>
<span class="normal">        </span><span class="keyword">return</span><span class="normal"> sum</span><span class="symbol">;</span>
<span class="normal">    </span><span class="cbracket">}</span>

<span class="normal">    </span><span class="comment">/**</span>
<span class="comment">     * Returns the optimal row strategy of this two-person zero-sum game.</span>
<span class="comment">     *</span>
<span class="comment">     * </span><span class="type">@return</span><span class="comment"> the optimal row strategy </span><span class="keyword">&lt;em&gt;</span><span class="comment">x</span><span class="keyword">&lt;/em&gt;</span><span class="comment"> of this two-person zero-sum game</span>
<span class="comment">     */</span>
<span class="normal">    </span><span class="keyword">public</span><span class="normal"> </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> </span><span class="function">row</span><span class="symbol">()</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="type">double</span><span class="normal"> scale </span><span class="symbol">=</span><span class="normal"> </span><span class="function">scale</span><span class="symbol">();</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> x </span><span class="symbol">=</span><span class="normal"> lp</span><span class="symbol">.</span><span class="function">primal</span><span class="symbol">();</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> j </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> j </span><span class="symbol">&lt;</span><span class="normal"> N</span><span class="symbol">;</span><span class="normal"> j</span><span class="symbol">++)</span>
<span class="normal">            x</span><span class="symbol">[</span><span class="normal">j</span><span class="symbol">]</span><span class="normal"> </span><span class="symbol">/=</span><span class="normal"> scale</span><span class="symbol">;</span>
<span class="normal">        </span><span class="keyword">return</span><span class="normal"> x</span><span class="symbol">;</span>
<span class="normal">    </span><span class="cbracket">}</span>

<span class="normal">    </span><span class="comment">/**</span>
<span class="comment">     * Returns the optimal column strategy of this two-person zero-sum game.</span>
<span class="comment">     *</span>
<span class="comment">     * </span><span class="type">@return</span><span class="comment"> the optimal column strategy </span><span class="keyword">&lt;em&gt;</span><span class="comment">y</span><span class="keyword">&lt;/em&gt;</span><span class="comment"> of this two-person zero-sum game</span>
<span class="comment">     */</span>
<span class="normal">    </span><span class="keyword">public</span><span class="normal"> </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> </span><span class="function">column</span><span class="symbol">()</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="type">double</span><span class="normal"> scale </span><span class="symbol">=</span><span class="normal"> </span><span class="function">scale</span><span class="symbol">();</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> y </span><span class="symbol">=</span><span class="normal"> lp</span><span class="symbol">.</span><span class="function">dual</span><span class="symbol">();</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> i </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> i </span><span class="symbol">&lt;</span><span class="normal"> M</span><span class="symbol">;</span><span class="normal"> i</span><span class="symbol">++)</span>
<span class="normal">            y</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">]</span><span class="normal"> </span><span class="symbol">/=</span><span class="normal"> scale</span><span class="symbol">;</span>
<span class="normal">        </span><span class="keyword">return</span><span class="normal"> y</span><span class="symbol">;</span>
<span class="normal">    </span><span class="cbracket">}</span>


<span class="normal">    </span><span class="comment">/**************************************************************************</span>
<span class="comment">     *</span>
<span class="comment">     *  The code below is solely for testing correctness of the data type.</span>
<span class="comment">     *</span>
<span class="comment">     **************************************************************************/</span>

<span class="normal">    </span><span class="comment">// is the row vector x primal feasible?</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="type">boolean</span><span class="normal"> </span><span class="function">isPrimalFeasible</span><span class="symbol">()</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> x </span><span class="symbol">=</span><span class="normal"> </span><span class="function">row</span><span class="symbol">();</span>
<span class="normal">        </span><span class="type">double</span><span class="normal"> sum </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0.0</span><span class="symbol">;</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> j </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> j </span><span class="symbol">&lt;</span><span class="normal"> N</span><span class="symbol">;</span><span class="normal"> j</span><span class="symbol">++)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            </span><span class="keyword">if</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">x</span><span class="symbol">[</span><span class="normal">j</span><span class="symbol">]</span><span class="normal"> </span><span class="symbol">&lt;</span><span class="normal"> </span><span class="number">0</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">                StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="string">"row vector not a probability distribution"</span><span class="symbol">);</span>
<span class="normal">                StdOut</span><span class="symbol">.</span><span class="function">printf</span><span class="symbol">(</span><span class="string">"    x[%d] = %f</span><span class="specialchar">\n</span><span class="string">"</span><span class="normal"> </span><span class="symbol">,</span><span class="normal"> j</span><span class="symbol">,</span><span class="normal"> x</span><span class="symbol">[</span><span class="normal">j</span><span class="symbol">]);</span>
<span class="normal">                </span><span class="keyword">return</span><span class="normal"> </span><span class="keyword">false</span><span class="symbol">;</span>
<span class="normal">            </span><span class="cbracket">}</span>
<span class="normal">            sum </span><span class="symbol">+=</span><span class="normal"> x</span><span class="symbol">[</span><span class="normal">j</span><span class="symbol">];</span>
<span class="normal">        </span><span class="cbracket">}</span>
<span class="normal">        </span><span class="keyword">if</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">Math</span><span class="symbol">.</span><span class="function">abs</span><span class="symbol">(</span><span class="normal">sum </span><span class="symbol">-</span><span class="normal"> </span><span class="number">1.0</span><span class="symbol">)</span><span class="normal"> </span><span class="symbol">&gt;</span><span class="normal"> EPSILON</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="string">"row vector x[] is not a probability distribution"</span><span class="symbol">);</span>
<span class="normal">            StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="string">"    sum = "</span><span class="normal"> </span><span class="symbol">+</span><span class="normal"> sum</span><span class="symbol">);</span>
<span class="normal">            </span><span class="keyword">return</span><span class="normal"> </span><span class="keyword">false</span><span class="symbol">;</span>
<span class="normal">        </span><span class="cbracket">}</span>
<span class="normal">        </span><span class="keyword">return</span><span class="normal"> </span><span class="keyword">true</span><span class="symbol">;</span>
<span class="normal">    </span><span class="cbracket">}</span>

<span class="normal">    </span><span class="comment">// is the column vector y dual feasible?</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="type">boolean</span><span class="normal"> </span><span class="function">isDualFeasible</span><span class="symbol">()</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> y </span><span class="symbol">=</span><span class="normal"> </span><span class="function">column</span><span class="symbol">();</span>
<span class="normal">        </span><span class="type">double</span><span class="normal"> sum </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0.0</span><span class="symbol">;</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> i </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> i </span><span class="symbol">&lt;</span><span class="normal"> M</span><span class="symbol">;</span><span class="normal"> i</span><span class="symbol">++)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            </span><span class="keyword">if</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">y</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">]</span><span class="normal"> </span><span class="symbol">&lt;</span><span class="normal"> </span><span class="number">0</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">                StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="string">"column vector y[] is not a probability distribution"</span><span class="symbol">);</span>
<span class="normal">                StdOut</span><span class="symbol">.</span><span class="function">printf</span><span class="symbol">(</span><span class="string">"    y[%d] = %f</span><span class="specialchar">\n</span><span class="string">"</span><span class="normal"> </span><span class="symbol">,</span><span class="normal"> i</span><span class="symbol">,</span><span class="normal"> y</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">]);</span>
<span class="normal">                </span><span class="keyword">return</span><span class="normal"> </span><span class="keyword">false</span><span class="symbol">;</span>
<span class="normal">            </span><span class="cbracket">}</span>
<span class="normal">            sum </span><span class="symbol">+=</span><span class="normal"> y</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">];</span>
<span class="normal">        </span><span class="cbracket">}</span>
<span class="normal">        </span><span class="keyword">if</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">Math</span><span class="symbol">.</span><span class="function">abs</span><span class="symbol">(</span><span class="normal">sum </span><span class="symbol">-</span><span class="normal"> </span><span class="number">1.0</span><span class="symbol">)</span><span class="normal"> </span><span class="symbol">&gt;</span><span class="normal"> EPSILON</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="string">"column vector not a probability distribution"</span><span class="symbol">);</span>
<span class="normal">            StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="string">"    sum = "</span><span class="normal"> </span><span class="symbol">+</span><span class="normal"> sum</span><span class="symbol">);</span>
<span class="normal">            </span><span class="keyword">return</span><span class="normal"> </span><span class="keyword">false</span><span class="symbol">;</span>
<span class="normal">        </span><span class="cbracket">}</span>
<span class="normal">        </span><span class="keyword">return</span><span class="normal"> </span><span class="keyword">true</span><span class="symbol">;</span>
<span class="normal">    </span><span class="cbracket">}</span>

<span class="normal">    </span><span class="comment">// is the solution a Nash equilibrium?</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="type">boolean</span><span class="normal"> </span><span class="function">isNashEquilibrium</span><span class="symbol">(</span><span class="type">double</span><span class="symbol">[][]</span><span class="normal"> payoff</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> x </span><span class="symbol">=</span><span class="normal"> </span><span class="function">row</span><span class="symbol">();</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> y </span><span class="symbol">=</span><span class="normal"> </span><span class="function">column</span><span class="symbol">();</span>
<span class="normal">        </span><span class="type">double</span><span class="normal"> value </span><span class="symbol">=</span><span class="normal"> </span><span class="function">value</span><span class="symbol">();</span>

<span class="normal">        </span><span class="comment">// given row player's mixed strategy, find column player's best pure strategy</span>
<span class="normal">        </span><span class="type">double</span><span class="normal"> opt1 </span><span class="symbol">=</span><span class="normal"> Double</span><span class="symbol">.</span><span class="normal">NEGATIVE_INFINITY</span><span class="symbol">;</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> i </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> i </span><span class="symbol">&lt;</span><span class="normal"> M</span><span class="symbol">;</span><span class="normal"> i</span><span class="symbol">++)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            </span><span class="type">double</span><span class="normal"> sum </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0.0</span><span class="symbol">;</span>
<span class="normal">            </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> j </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> j </span><span class="symbol">&lt;</span><span class="normal"> N</span><span class="symbol">;</span><span class="normal"> j</span><span class="symbol">++)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">                sum </span><span class="symbol">+=</span><span class="normal"> payoff</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">][</span><span class="normal">j</span><span class="symbol">]</span><span class="normal"> </span><span class="symbol">*</span><span class="normal"> x</span><span class="symbol">[</span><span class="normal">j</span><span class="symbol">];</span>
<span class="normal">            </span><span class="cbracket">}</span>
<span class="normal">            </span><span class="keyword">if</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">sum </span><span class="symbol">&gt;</span><span class="normal"> opt1</span><span class="symbol">)</span><span class="normal"> opt1 </span><span class="symbol">=</span><span class="normal"> sum</span><span class="symbol">;</span>
<span class="normal">        </span><span class="cbracket">}</span>
<span class="normal">        </span><span class="keyword">if</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">Math</span><span class="symbol">.</span><span class="function">abs</span><span class="symbol">(</span><span class="normal">opt1 </span><span class="symbol">-</span><span class="normal"> value</span><span class="symbol">)</span><span class="normal"> </span><span class="symbol">&gt;</span><span class="normal"> EPSILON</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="string">"Optimal value = "</span><span class="normal"> </span><span class="symbol">+</span><span class="normal"> value</span><span class="symbol">);</span>
<span class="normal">            StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="string">"Optimal best response for column player = "</span><span class="normal"> </span><span class="symbol">+</span><span class="normal"> opt1</span><span class="symbol">);</span>
<span class="normal">            </span><span class="keyword">return</span><span class="normal"> </span><span class="keyword">false</span><span class="symbol">;</span>
<span class="normal">        </span><span class="cbracket">}</span>

<span class="normal">        </span><span class="comment">// given column player's mixed strategy, find row player's best pure strategy</span>
<span class="normal">        </span><span class="type">double</span><span class="normal"> opt2 </span><span class="symbol">=</span><span class="normal"> Double</span><span class="symbol">.</span><span class="normal">POSITIVE_INFINITY</span><span class="symbol">;</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> j </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> j </span><span class="symbol">&lt;</span><span class="normal"> N</span><span class="symbol">;</span><span class="normal"> j</span><span class="symbol">++)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            </span><span class="type">double</span><span class="normal"> sum </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0.0</span><span class="symbol">;</span>
<span class="normal">            </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> i </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> i </span><span class="symbol">&lt;</span><span class="normal"> M</span><span class="symbol">;</span><span class="normal"> i</span><span class="symbol">++)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">                sum </span><span class="symbol">+=</span><span class="normal"> payoff</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">][</span><span class="normal">j</span><span class="symbol">]</span><span class="normal"> </span><span class="symbol">*</span><span class="normal"> y</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">];</span>
<span class="normal">            </span><span class="cbracket">}</span>
<span class="normal">            </span><span class="keyword">if</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">sum </span><span class="symbol">&lt;</span><span class="normal"> opt2</span><span class="symbol">)</span><span class="normal"> opt2 </span><span class="symbol">=</span><span class="normal"> sum</span><span class="symbol">;</span>
<span class="normal">        </span><span class="cbracket">}</span>
<span class="normal">        </span><span class="keyword">if</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">Math</span><span class="symbol">.</span><span class="function">abs</span><span class="symbol">(</span><span class="normal">opt2 </span><span class="symbol">-</span><span class="normal"> value</span><span class="symbol">)</span><span class="normal"> </span><span class="symbol">&gt;</span><span class="normal"> EPSILON</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="string">"Optimal value = "</span><span class="normal"> </span><span class="symbol">+</span><span class="normal"> value</span><span class="symbol">);</span>
<span class="normal">            StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="string">"Optimal best response for row player = "</span><span class="normal"> </span><span class="symbol">+</span><span class="normal"> opt2</span><span class="symbol">);</span>
<span class="normal">            </span><span class="keyword">return</span><span class="normal"> </span><span class="keyword">false</span><span class="symbol">;</span>
<span class="normal">        </span><span class="cbracket">}</span>


<span class="normal">        </span><span class="keyword">return</span><span class="normal"> </span><span class="keyword">true</span><span class="symbol">;</span>
<span class="normal">    </span><span class="cbracket">}</span>

<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="type">boolean</span><span class="normal"> </span><span class="function">certifySolution</span><span class="symbol">(</span><span class="type">double</span><span class="symbol">[][]</span><span class="normal"> payoff</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="keyword">return</span><span class="normal"> </span><span class="function">isPrimalFeasible</span><span class="symbol">()</span><span class="normal"> </span><span class="symbol">&amp;&amp;</span><span class="normal"> </span><span class="function">isDualFeasible</span><span class="symbol">()</span><span class="normal"> </span><span class="symbol">&amp;&amp;</span><span class="normal"> </span><span class="function">isNashEquilibrium</span><span class="symbol">(</span><span class="normal">payoff</span><span class="symbol">);</span>
<span class="normal">    </span><span class="cbracket">}</span>


<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="keyword">static</span><span class="normal"> </span><span class="type">void</span><span class="normal"> </span><span class="function">test</span><span class="symbol">(</span><span class="usertype">String</span><span class="normal"> description</span><span class="symbol">,</span><span class="normal"> </span><span class="type">double</span><span class="symbol">[][]</span><span class="normal"> payoff</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">();</span>
<span class="normal">        StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="normal">description</span><span class="symbol">);</span>
<span class="normal">        StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="string">"------------------------------------"</span><span class="symbol">);</span>
<span class="normal">        </span><span class="type">int</span><span class="normal"> M </span><span class="symbol">=</span><span class="normal"> payoff</span><span class="symbol">.</span><span class="normal">length</span><span class="symbol">;</span>
<span class="normal">        </span><span class="type">int</span><span class="normal"> N </span><span class="symbol">=</span><span class="normal"> payoff</span><span class="symbol">[</span><span class="number">0</span><span class="symbol">].</span><span class="normal">length</span><span class="symbol">;</span>
<span class="normal">        </span><span class="usertype">TwoPersonZeroSumGame</span><span class="normal"> zerosum </span><span class="symbol">=</span><span class="normal"> </span><span class="keyword">new</span><span class="normal"> </span><span class="function">TwoPersonZeroSumGame</span><span class="symbol">(</span><span class="normal">payoff</span><span class="symbol">);</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> x </span><span class="symbol">=</span><span class="normal"> zerosum</span><span class="symbol">.</span><span class="function">row</span><span class="symbol">();</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[]</span><span class="normal"> y </span><span class="symbol">=</span><span class="normal"> zerosum</span><span class="symbol">.</span><span class="function">column</span><span class="symbol">();</span>

<span class="normal">        StdOut</span><span class="symbol">.</span><span class="function">print</span><span class="symbol">(</span><span class="string">"x[] = ["</span><span class="symbol">);</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> j </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> j </span><span class="symbol">&lt;</span><span class="normal"> N</span><span class="symbol">-</span><span class="number">1</span><span class="symbol">;</span><span class="normal"> j</span><span class="symbol">++)</span>
<span class="normal">            StdOut</span><span class="symbol">.</span><span class="function">printf</span><span class="symbol">(</span><span class="string">"%8.4f, "</span><span class="symbol">,</span><span class="normal"> x</span><span class="symbol">[</span><span class="normal">j</span><span class="symbol">]);</span>
<span class="normal">        StdOut</span><span class="symbol">.</span><span class="function">printf</span><span class="symbol">(</span><span class="string">"%8.4f]</span><span class="specialchar">\n</span><span class="string">"</span><span class="symbol">,</span><span class="normal"> x</span><span class="symbol">[</span><span class="normal">N</span><span class="symbol">-</span><span class="number">1</span><span class="symbol">]);</span>

<span class="normal">        StdOut</span><span class="symbol">.</span><span class="function">print</span><span class="symbol">(</span><span class="string">"y[] = ["</span><span class="symbol">);</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> i </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> i </span><span class="symbol">&lt;</span><span class="normal"> M</span><span class="symbol">-</span><span class="number">1</span><span class="symbol">;</span><span class="normal"> i</span><span class="symbol">++)</span>
<span class="normal">            StdOut</span><span class="symbol">.</span><span class="function">printf</span><span class="symbol">(</span><span class="string">"%8.4f, "</span><span class="symbol">,</span><span class="normal"> y</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">]);</span>
<span class="normal">        StdOut</span><span class="symbol">.</span><span class="function">printf</span><span class="symbol">(</span><span class="string">"%8.4f]</span><span class="specialchar">\n</span><span class="string">"</span><span class="symbol">,</span><span class="normal"> y</span><span class="symbol">[</span><span class="normal">M</span><span class="symbol">-</span><span class="number">1</span><span class="symbol">]);</span>
<span class="normal">        StdOut</span><span class="symbol">.</span><span class="function">println</span><span class="symbol">(</span><span class="string">"value =  "</span><span class="normal"> </span><span class="symbol">+</span><span class="normal"> zerosum</span><span class="symbol">.</span><span class="function">value</span><span class="symbol">());</span>
<span class="normal">        </span>
<span class="normal">    </span><span class="cbracket">}</span>

<span class="normal">    </span><span class="comment">// row = { 4/7, 3/7 }, column = { 0, 4/7, 3/7 }, value = 20/7</span>
<span class="normal">    </span><span class="comment">// http://en.wikipedia.org/wiki/Zero-sum</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="keyword">static</span><span class="normal"> </span><span class="type">void</span><span class="normal"> </span><span class="function">test1</span><span class="symbol">()</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[][]</span><span class="normal"> payoff </span><span class="symbol">=</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal"> </span><span class="number">30</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">10</span><span class="symbol">,</span><span class="normal">  </span><span class="number">20</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal"> </span><span class="number">10</span><span class="symbol">,</span><span class="normal">  </span><span class="number">20</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">20</span><span class="normal"> </span><span class="cbracket">}</span>
<span class="normal">        </span><span class="cbracket">}</span><span class="symbol">;</span>
<span class="normal">        </span><span class="function">test</span><span class="symbol">(</span><span class="string">"wikipedia"</span><span class="symbol">,</span><span class="normal"> payoff</span><span class="symbol">);</span>
<span class="normal">    </span><span class="cbracket">}</span>

<span class="normal">    </span><span class="comment">// skew-symmetric =&gt; value = 0</span>
<span class="normal">    </span><span class="comment">// Linear Programming by Chvatal, p. 230</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="keyword">static</span><span class="normal"> </span><span class="type">void</span><span class="normal"> </span><span class="function">test2</span><span class="symbol">()</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[][]</span><span class="normal"> payoff </span><span class="symbol">=</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">2</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">3</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal"> </span><span class="symbol">-</span><span class="number">2</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">3</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">3</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">4</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">3</span><span class="symbol">,</span><span class="normal">  </span><span class="number">4</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="normal"> </span><span class="cbracket">}</span>
<span class="normal">        </span><span class="cbracket">}</span><span class="symbol">;</span>
<span class="normal">        </span><span class="function">test</span><span class="symbol">(</span><span class="string">"Chvatal, p. 230"</span><span class="symbol">,</span><span class="normal"> payoff</span><span class="symbol">);</span>
<span class="normal">    </span><span class="cbracket">}</span>

<span class="normal">    </span><span class="comment">// Linear Programming by Chvatal, p. 234</span>
<span class="normal">    </span><span class="comment">// row    = { 0, 56/99, 40/99, 0, 0, 2/99, 0, 1/99 }</span>
<span class="normal">    </span><span class="comment">// column = { 28/99, 30/99, 21/99, 20/99 }</span>
<span class="normal">    </span><span class="comment">// value  = 4/99</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="keyword">static</span><span class="normal"> </span><span class="type">void</span><span class="normal"> </span><span class="function">test3</span><span class="symbol">()</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[][]</span><span class="normal"> payoff </span><span class="symbol">=</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">2</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">3</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal"> </span><span class="symbol">-</span><span class="number">2</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">3</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">3</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">4</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">3</span><span class="symbol">,</span><span class="normal">  </span><span class="number">4</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">3</span><span class="symbol">,</span><span class="normal">  </span><span class="number">3</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal"> </span><span class="symbol">-</span><span class="number">2</span><span class="symbol">,</span><span class="normal">  </span><span class="number">2</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">3</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">3</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">4</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">4</span><span class="normal"> </span><span class="cbracket">}</span>
<span class="normal">        </span><span class="cbracket">}</span><span class="symbol">;</span>
<span class="normal">        </span><span class="function">test</span><span class="symbol">(</span><span class="string">"Chvatal, p. 234"</span><span class="symbol">,</span><span class="normal"> payoff</span><span class="symbol">);</span>
<span class="normal">    </span><span class="cbracket">}</span>

<span class="normal">    </span><span class="comment">// Linear Programming by Chvatal, p. 236</span>
<span class="normal">    </span><span class="comment">// row    = { 0, 2/5, 7/15, 0, 2/15, 0, 0, 0 }</span>
<span class="normal">    </span><span class="comment">// column = { 2/3, 0, 0, 1/3 }</span>
<span class="normal">    </span><span class="comment">// value  = -1/3</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="keyword">static</span><span class="normal"> </span><span class="type">void</span><span class="normal"> </span><span class="function">test4</span><span class="symbol">()</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[][]</span><span class="normal"> payoff </span><span class="symbol">=</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">2</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">1</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">2</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="symbol">,</span><span class="normal">  </span><span class="number">1</span><span class="symbol">,</span><span class="normal">  </span><span class="number">1</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal">  </span><span class="number">1</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">1</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">2</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">3</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">1</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">3</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">3</span><span class="symbol">,</span><span class="normal">  </span><span class="number">2</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">2</span><span class="symbol">,</span><span class="normal">  </span><span class="number">1</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">        </span><span class="cbracket">}</span><span class="symbol">;</span>
<span class="normal">        </span><span class="function">test</span><span class="symbol">(</span><span class="string">"Chvatal p. 236"</span><span class="symbol">,</span><span class="normal"> payoff</span><span class="symbol">);</span>
<span class="normal">    </span><span class="cbracket">}</span>

<span class="normal">    </span><span class="comment">// rock, paper, scissors</span>
<span class="normal">    </span><span class="comment">// row    = { 1/3, 1/3, 1/3 }</span>
<span class="normal">    </span><span class="comment">// column = { 1/3, 1/3, 1/3 }</span>
<span class="normal">    </span><span class="keyword">private</span><span class="normal"> </span><span class="keyword">static</span><span class="normal"> </span><span class="type">void</span><span class="normal"> </span><span class="function">test5</span><span class="symbol">()</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[][]</span><span class="normal"> payoff </span><span class="symbol">=</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="symbol">,</span><span class="normal">  </span><span class="number">1</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal">  </span><span class="number">1</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="symbol">,</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="normal"> </span><span class="cbracket">}</span><span class="symbol">,</span>
<span class="normal">            </span><span class="cbracket">{</span><span class="normal"> </span><span class="symbol">-</span><span class="number">1</span><span class="symbol">,</span><span class="normal">  </span><span class="number">1</span><span class="symbol">,</span><span class="normal">  </span><span class="number">0</span><span class="normal"> </span><span class="cbracket">}</span>
<span class="normal">        </span><span class="cbracket">}</span><span class="symbol">;</span>
<span class="normal">        </span><span class="function">test</span><span class="symbol">(</span><span class="string">"rock, paper, scisssors"</span><span class="symbol">,</span><span class="normal"> payoff</span><span class="symbol">);</span>
<span class="normal">    </span><span class="cbracket">}</span>


<span class="normal">    </span><span class="comment">/**</span>
<span class="comment">     * Unit tests the </span><span class="keyword">&lt;tt&gt;</span><span class="comment">ZeroSumGameToLP</span><span class="keyword">&lt;/tt&gt;</span><span class="comment"> data type.</span>
<span class="comment">     */</span>
<span class="normal">    </span><span class="keyword">public</span><span class="normal"> </span><span class="keyword">static</span><span class="normal"> </span><span class="type">void</span><span class="normal"> </span><span class="function">main</span><span class="symbol">(</span><span class="normal">String</span><span class="symbol">[]</span><span class="normal"> args</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal">        </span><span class="function">test1</span><span class="symbol">();</span>
<span class="normal">        </span><span class="function">test2</span><span class="symbol">();</span>
<span class="normal">        </span><span class="function">test3</span><span class="symbol">();</span>
<span class="normal">        </span><span class="function">test4</span><span class="symbol">();</span>
<span class="normal">        </span><span class="function">test5</span><span class="symbol">();</span>

<span class="normal">        </span><span class="type">int</span><span class="normal"> M </span><span class="symbol">=</span><span class="normal"> Integer</span><span class="symbol">.</span><span class="function">parseInt</span><span class="symbol">(</span><span class="normal">args</span><span class="symbol">[</span><span class="number">0</span><span class="symbol">]);</span>
<span class="normal">        </span><span class="type">int</span><span class="normal"> N </span><span class="symbol">=</span><span class="normal"> Integer</span><span class="symbol">.</span><span class="function">parseInt</span><span class="symbol">(</span><span class="normal">args</span><span class="symbol">[</span><span class="number">1</span><span class="symbol">]);</span>
<span class="normal">        </span><span class="type">double</span><span class="symbol">[][]</span><span class="normal"> payoff </span><span class="symbol">=</span><span class="normal"> </span><span class="keyword">new</span><span class="normal"> </span><span class="type">double</span><span class="symbol">[</span><span class="normal">M</span><span class="symbol">][</span><span class="normal">N</span><span class="symbol">];</span>
<span class="normal">        </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> i </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> i </span><span class="symbol">&lt;</span><span class="normal"> M</span><span class="symbol">;</span><span class="normal"> i</span><span class="symbol">++)</span>
<span class="normal">            </span><span class="keyword">for</span><span class="normal"> </span><span class="symbol">(</span><span class="type">int</span><span class="normal"> j </span><span class="symbol">=</span><span class="normal"> </span><span class="number">0</span><span class="symbol">;</span><span class="normal"> j </span><span class="symbol">&lt;</span><span class="normal"> N</span><span class="symbol">;</span><span class="normal"> j</span><span class="symbol">++)</span>
<span class="normal">                payoff</span><span class="symbol">[</span><span class="normal">i</span><span class="symbol">][</span><span class="normal">j</span><span class="symbol">]</span><span class="normal"> </span><span class="symbol">=</span><span class="normal"> StdRandom</span><span class="symbol">.</span><span class="function">uniform</span><span class="symbol">(-</span><span class="number">0.5</span><span class="symbol">,</span><span class="normal"> </span><span class="number">0.5</span><span class="symbol">);</span>
<span class="normal">        </span><span class="function">test</span><span class="symbol">(</span><span class="string">"random "</span><span class="normal"> </span><span class="symbol">+</span><span class="normal"> M </span><span class="symbol">+</span><span class="normal"> </span><span class="string">"-by-"</span><span class="normal"> </span><span class="symbol">+</span><span class="normal"> N</span><span class="symbol">,</span><span class="normal"> payoff</span><span class="symbol">);</span>
<span class="normal">    </span><span class="cbracket">}</span>

<span class="cbracket">}</span>

<span class="comment">/******************************************************************************</span>
<span class="comment"> *  Copyright 2002-2015, Robert Sedgewick and Kevin Wayne.</span>
<span class="comment"> *</span>
<span class="comment"> *  This file is part of algs4.jar, which accompanies the textbook</span>
<span class="comment"> *</span>
<span class="comment"> *      Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,</span>
<span class="comment"> *      Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.</span>
<span class="comment"> *      </span><span class="url">http://algs4.cs.princeton.edu</span>
<span class="comment"> *</span>
<span class="comment"> *</span>
<span class="comment"> *  algs4.jar is free software: you can redistribute it and/or modify</span>
<span class="comment"> *  it under the terms of the GNU General Public License as published by</span>
<span class="comment"> *  the Free Software Foundation, either version 3 of the License, or</span>
<span class="comment"> *  (at your option) any later version.</span>
<span class="comment"> *</span>
<span class="comment"> *  algs4.jar is distributed in the hope that it will be useful,</span>
<span class="comment"> *  but WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<span class="comment"> *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the</span>
<span class="comment"> *  GNU General Public License for more details.</span>
<span class="comment"> *</span>
<span class="comment"> *  You should have received a copy of the GNU General Public License</span>
<span class="comment"> *  along with algs4.jar.  If not, see </span><span class="url">http://www.gnu.org/licenses.</span>
<span class="comment"> ******************************************************************************/</span>
</tt></pre>

<script type="text/javascript">
var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
</script>
<script type="text/javascript">
try {
var pageTracker = _gat._getTracker("UA-10811519-2");
pageTracker._trackPageview();
} catch(err) {}</script>

</body>

<p><br><address><small>
Last updated: Mon Mar 21 10:51:08 EDT 2016.
</small></address>

</html>
